package com.gwcloud.leetcode.hot100;

import com.gwcloud.leetcode.common.datastructure.ListNode;

/** 
* @ClassName   : Leetcode0142 
* @author      : ganwei 
* @date        : 2020年5月21日 
* @Description : 142. 环形链表 II 
*/
public class Leetcode0142 {
	/**
	 * -解题思路，快慢指针
	 */
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
        	fast = fast.next.next;
        	slow = slow.next;
        	if(slow == fast) {
        		break;
        	}
        }
        if(fast == null || fast.next == null){
            return null;
        }

        slow = head;
        while(slow != fast ) {
        	slow = slow.next;
        	fast = fast.next;
        }
        
    	return slow;
    }
    
    /**
     * -主函数
     */
    public static void main(String[] args) {
    	ListNode n1 = new ListNode(3);
    	ListNode n2 = new ListNode(2);
    	ListNode n3 = new ListNode(0);
    	ListNode n4 = new ListNode(-4);
    	
    	n1.next = n2;
    	n2.next = n3;
    	n3.next = n4;
    	n4.next = n2;
    	
    	
    }
}
